//二叉树的最近公共祖先（递归）
class Solution {
public:
    //递归解法
    bool IsInTree(TreeNode* t,TreeNode* x)
    {
        if(t == nullptr)
            return false;
        
        return t == x
            || IsInTree(t->left,x)
            || IsInTree(t->right,x);
    }

    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root == nullptr)
            return nullptr;
        
        //当p或者q为子树的根时，根结点就是最近公共祖先
        if(root == q || root == p)
            return root;

        bool pIsInLeft = IsInTree(root->left,p);
        bool pIsInRight = !pIsInLeft;
        bool qIsInLeft = IsInTree(root->left,q);
        bool qIsInRight = !qIsInLeft;

        //1.当q p在根结点的一左一右 此时根结点就是最近公共祖先
        if((pIsInLeft && qIsInRight) || (pIsInRight && qIsInLeft))
            return root;
        //2.当两个结点都在左子树中 递归到左子树中查找
        else if(pIsInLeft && qIsInLeft)
            return lowestCommonAncestor(root->left,q,p);
        //3.当两个结点都在右子树中 递归到右子树中查找
        else
            return lowestCommonAncestor(root->right,q,p);
    }
};


//递归用一个栈记录结点的路径
class Solution {
public:
    bool GetPath(TreeNode* cur,TreeNode* x,stack<TreeNode*>& st)
    {
        if(cur == nullptr)
            return false;
        
        st.push(cur);

        if(cur == x)
            return true;

        if(GetPath(cur->left,x,st))
            return true;
        
        if(GetPath(cur->right,x,st))
            return true;

        st.pop();
        return false;
    }

    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        stack<TreeNode*> st1;
        stack<TreeNode*> st2;
        GetPath(root,p,st1);
        GetPath(root,q,st2);
        
        int i=st1.size(),j = st2.size();
        while(st1.top() != st2.top())
        {
            if(i > j)
            {
                st1.pop();
                --i;
            }
            else if(i < j)
            {
                st2.pop();
                --j;
            }
            else
            {
                st1.pop();
                st2.pop();
                --i;
                --j;
            }
        }
        return st1.top();
    }
};
